package com.cty.prim;

/*
 *
 * 普利姆算法解决修路问题
 *
 *
 * */
public class Prim {
    public void minTree(Graph graph,int v) {
        boolean[] isVisited = new boolean[graph.vertxs];
        isVisited[v] = true;
        int minWeight = 10000;
        int h1 = -1;
        int h2 = -1;
        for (int k = 1;k < graph.vertxs;k++) {
            for (int i = 0;i < graph.vertxs;i++) {
                for (int j = 0;j < graph.vertxs;j++) {
                    if (isVisited[i] == true && isVisited[j] == false && graph.weight[i][j] < minWeight) {
                        minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            isVisited[h2] = true;
            System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + ">" + "修路长度" + minWeight);
            minWeight = 10000;
        }
    }
}
